In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Słynna producent czekolady z Plovdiv, Bonny, musi pociąć tabliczkę czekolady z rodzynkami. Czekolada jest prostokątem składającym się z jednakowych, kwadratowych kawałków. Kawałki są ułożone równolegle do krawędzi czekolady w rzędach i kolumnach, co daje łącznie kawałków. Każdy z kawałków zawiera pewną dodatnią liczbę rodzynek, a żadne rodzynki nie leżą na liniach oddzielających kawałki.
Początkowo czekolada jest w całości. Bonny chce ją ciąć na coraz mniejsze fragmenty, aż w końcu otrzyma czekoladę podzieloną na pojedynczych kawałków. Ponieważ Bonny jest bardzo zajęta, do pomocy przy cięciu potrzebuje pomocy swego asystenta, Chytrego Piotra. Piotr tnie czekoladę po prostych, od brzegu do brzegu, i oczekuje zapłaty za każde wykonane cięcie. Bonny chwilowo nie posiada pieniędzy, ma za to sporo rodzynek, które nie zostały użyte, więc oferuje Piotrowi zapłatę w rodzynkach. Chytry Piotr zgadza się, ale pod warunkiem, że za każde przecięcie fragmentu czekolady na dwa mniejsze dostanie tyle rodzynek, ile jest ich łącznie w tym fragmencie.
Bonny chciałaby dać Piotrowi jak najmniej rodzynek. Wie dokładnie, ile rodzynek jest w każdym z kawałków. Może też zadecydować o kolejności, w której będzie podawać Piotrowi fragmenty czekolady, a także kazać mu wykonywać cięcia w konkretnym kierunku (w pionie lub poziomie) i wzdłuż konkretnej linii. Pomóż Bonny znaleźć taki sposób cięcia czekolady na pojedyncze kawałki, żeby zapłaciła Chytremu Piotrowi jak najmniej rodzynek.
Napisz program, który mając dane liczby rodzynek w poszczególnych kawałkach czekolady, wyznaczy minimalną liczbę rodzynek, które Bonny będzie musiała oddać Chytremu Piotrowi.
- liczby kawałków na każdym z boków czekolady
- liczba rodzynek w kawałku czekolady w -tym wierszu i -tej kolumnie
Twój program powinien wczytać ze standardowego wejścia następujące dane:
Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający jedną liczbę całkowitą: minimalną liczbę rodzynek, które Bonny musi oddać Chytremu Piotrowi.
W testach wartych łącznie 25 punktów i nie przekroczą 7.
Dla danych wejściowych:
2 3 2 7 5 1 9 5
poprawną odpowiedzią jest:
77
Wyjaśnienie do przykładu: oto jeden z możliwych sposobów (spośród wielu) osiągnięcia kosztu 77 rodzynek.
Pierwszym cięciem, o które prosi Piotra Bonny, jest oddzielenie trzeciej kolumny od reszty czekolady. Bonny płaci za to 29 rodzynek.
Następnie, Bonny daje Piotrowi mniejszy z fragmentów - ten złożony z dwóch kawałków zawierających po 5 rodzynek - a Piotr przecina go na pół za 10 rodzynek.
Później Bonny daje Piotrowi największy z pozostałych fragmentów - ten zawierający kawałki z 2, 7, 1 oraz 9 rodzynkami. Bonny prosi o poziome cięcie, które oddzieli pierwszy wiersz od drugiego, i płaci 19 rodzynek.
Następnie, Bonny daje Piotrowi lewy górny fragment, płacąc 9 rodzynek. W końcu Bonny prosi Piotra o podzielenie lewego dolnego fragmentu za 10 rodzynek.
Całkowity koszt, jaki ponosi Bonny, to rodzynek. Żaden inny schemat cięć nie podzieli tej czekolady na 6 kawałków mniejszym kosztem.